๐งท Memory Access
ํ๋ก๊ทธ๋จ์ ์คํ์ ์ํด ๋ฉ๋ชจ๋ฆฌ๋ก ๋ก๋๋์ด์ผ ํ๋ค.
-
CPU๋ ๋ ์ง์คํฐ์ ๋ฉ์ธ ๋ฉ๋ชจ๋ฆฌ์๋ง ์ ๊ทผํ ์ ์๋ค.
- ๋ ์ง์คํฐ: ์ ๊ทผํ๋๋ฐ ๋ณดํต 1 clock cycle์ด ์๋ชจ๋๋ค.
- ๋ฉ๋ชจ๋ฆฌ: ๋ช cycles์ด ์๋ชจ๋๋ค. (๋ฉ๋ชจ๋ฆฌ ๋ฒ์ค์์ ํธ๋์ญ์ ์ด CPU stall์ ๋ฐ์์ํจ๋ค.)
-
๋ฉ๋ชจ๋ฆฌ unit์ ๋ฉ๋ชจ๋ฆฌ ์ฃผ์๋ค์ ์คํธ๋ฆผ๋ง์ ํ์ธํ ์ ์๋ค.
- Context oblivious -> Context๋ฅผ ์์ง ๋ชปํ๋ค.
- ์ฆ, ์ด๋ป๊ฒ ์์ฑ๋๊ณ , ์ด๋ค ๋ฐ์ดํฐ๊ฐ ์๋์ง ์ ์ ์๋ค.
๐งท Address Binding
ํ๋ก์ธ์ค์ ์ฃผ์๋ ๋ ผ๋ฆฌ์ ์ฃผ์์ ๋ฌผ๋ฆฌ์ ์ฃผ์๋ก ๋๋๋ค.
-
๋ ผ๋ฆฌ์ ์ฃผ์๋ ๊ฐ์ ์ฃผ์๋ผ๊ณ ๋ ํ๋ฉฐ, CPU๊ฐ ์์ฑํ๋ ์ฃผ์์ด๋ค.
- ํ๋ก์ธ์ค๋ง๋ค ๋ ๋ฆฝ์ ์ผ๋ก ๊ฐ์ง๋ ์ฃผ์ ๊ณต๊ฐ์ด๋ฏ๋ก, ํ๋ก์ธ์ค์ ๋ด๋ถ์์ ์ฌ์ฉํ๊ณ , ๊ฐ ํ๋ก์ธ์ค๋ง๋ค 0๋ถํฐ ์์ํ๋ค.
- ๋ฌผ๋ฆฌ์ ์ฃผ์๋ ํ๋ก์ธ์ค๊ฐ ์คํ๋๊ธฐ ์ํด ์ค์ ๋ก ๋ฉ๋ก๋ฆฌ์ ์ฌ๋ผ๊ฐ๋ ์์น์ด๋ค.
Address Binding์ด๋, ์ด๋ค ํ๋ก๊ทธ๋จ์ด ๋ฉ๋ชจ๋ฆฌ์ ์ด๋ ์์น์, ์ฆ ์ด๋ค ๋ฌผ๋ฆฌ์ ์ฃผ์์ ๋ก๋๋ ์ง๋ฅผ ๊ฒฐ์ ํ๋ ๊ณผ์ ์ด๋ค.
- ๊ทธ๋ฆฌ๊ณ ์ด๋ Bindingํ๋ ์์ ์ ๋ฐ๋ผ ๋ถ๋ฅ๋๊ณ , ์๋๋ ํด๋น 3๊ฐ์ง ์์ ์ด๋ค.
๐ช Compile time
: ์ปดํ์ผ ๋์ ์ ํด์ง๋ค. ํ๋ก์ธ์ค๊ฐ ๋ฉ๋ชจ๋ฆฌ์ ์ด๋ ์์น์ ๋ค์ด๊ฐ์ง ๋ฏธ๋ฆฌ ์๊ณ ์๋ค๋ฉด, ์ปดํ์ผ๋ฌ๊ฐ ์ ๋ ์ฃผ์(Absolute address), ์ฆ ๊ณ ์ ๋ ์ฃผ์๋ฅผ ์์ฑํ๋ค.
- ๋ง์ฝ ์์น๊ฐ ๋ณ๊ฒฝ๋๋ค๋ฉด ์ฌ์ปดํ์ผ์ ํด์ผ ํ๋ค.
- ์ด๋ ํ๋ก์ธ์ค ๋ด๋ถ์์ ์ฌ์ฉํ๋ ๋ ผ๋ฆฌ์ ์ฃผ์์ ๋ฌผ๋ฆฌ์ ์ฃผ์๊ฐ ๋์ผํ๋ค.
- ๋ฌธ์ ์ ์ ๊ณ ์ ๋ ์ฃผ์๋ฅผ ์ฌ์ฉํ๊ธฐ์ ๋ฉ๋ชจ๋ฆฌ ์์ ๋น ๊ณต๊ฐ์ด ๋ง์ด ๋ฐ์ํ ์ ์์ด ๋นํจ์จ์ ์ด๊ณ , ๋ก๋ํ๋ ค๋ ์์น์ ์ด๋ฏธ ๋ค๋ฅธ ํ๋ก์ธ์ค๊ฐ ์กด์ฌํ ์ ์๋ค.
๐ช Load time
: ํ๋ก์ธ์ค๊ฐ ๋ฉ๋ชจ๋ฆฌ์ ์ด๋ ์์น์ ๋ค์ด๊ฐ์ง ๋ฏธ๋ฆฌ ์ ์ ์๋ค๋ฉด, ์ปดํ์ผ๋ฌ๋ Relocatable Code๋ฅผ ์์ฑํด์ผ ํ๋ค. ์ด๋ ๋ฉ๋ชจ๋ฆฌ์ ์ด๋ ์์น์์๋ ์ํ๋ ์ ์๋ ๊ธฐ๊ณ ์ธ์ด ์ฝ๋์ด๋ค.
- Loader๊ฐ ํ๋ก์ธ์ค๋ฅผ ๋ฉ๋ชจ๋ฆฌ์ ๋ก๋ํ๋ ์์ ์ ๋ฌผ๋ฆฌ์ ์ฃผ์๋ฅผ ๊ฒฐ์ ํ๋ค.
- ์ด๋ ๋ ผ๋ฆฌ์ ์ฃผ์์ ๋ฌผ๋ฆฌ์ ์ฃผ์๊ฐ ๋ค๋ฅด๋ค.
- ๋ฌธ์ ์ ์, ํ๋ก์ธ์ค ๋ด์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ฐธ์กฐํ๋ ๋ช ๋ น์ด๋ค์ด ๋ง์ ์ด๋ค์ ์ฃผ์๋ฅผ ๋ค ๋ฐ๊ฟ์ค์ผ ํ๊ธฐ์ ๋ก๋ฉํ ๋์ ์๊ฐ์ด ๋งค์ฐ ์ปค์ง ์ ์๋ค.
์ปดํ์ผ ํ์๊ณผ ๋ก๋ ํ์ ์ฃผ์ ํ ๋น์ ์ ์ฐ์ด์ง ์๋๋ค.
๐ช Execution time
: ํ๋ก์ธ์ค๊ฐ ๋์ํ๋ ๋์ ๋ฉ๋ชจ๋ฆฌ ์ฃผ์๋ฅผ ๋ฐ๊พธ๋ ๋ฐฉ๋ฒ์ด๋ค. ์ฆ ์คํ ๋์ค ๋ฌผ๋ฆฌ์ ์ฃผ์๊ฐ ๊ฒฐ์ ๋๋ฉฐ ์คํ ๋์ค์ ์ฃผ์๊ฐ ๋ฐ๋ ์๋ ์๋ค.
- MMU(Memory Management Unit)๋ผ๋ ํ๋์จ์ด ์ฅ์น๋ฅผ ์ฌ์ฉํด ๋ ผ๋ฆฌ์ ์ฃผ์๋ฅผ ๋ฌผ๋ฆฌ์ ์ฃผ์๋ก ๋ฐ๊ฟ์ค๋ค. (์ฃผ์ ์ฌ๋ฐฐ์น๊ฐ ๋น๋ฒํ๊ฒ ์ผ์ด๋๊ธฐ์ ํ๋์จ์ด์ ๋์์ด ํจ์จ์ ์ด๋ค.)
-
ํ๋ก์ธ์ค๊ฐ CPU์์ ์ํ๋๋ฉด์ ์์ฑํด๋ด๋ ๋ชจ๋ ์ฃผ์๊ฐ์ ๋ํด base register ๊ฐ(์ ๊ทผํ ์ ์๋ ๋ฌผ๋ฆฌ์ ์ฃผ์์ ์ต์๊ฐ)์ ๋ํด ๋ฌผ๋ฆฌ์ ์ฃผ์๋ฅผ ์์ฑํ๋ค.
- base register๋ ํ๋์ด๋ฏ๋ก ํ๋ก์ธ์ค ๊ฐ ๊ณต์ ํ๋ค.
- ๋ ผ๋ฆฌ์ ์ฃผ์์ ๋ฌผ๋ฆฌ์ ์ฃผ์๊ฐ ๋ค๋ฅด๋ค.
๐งท Dynamic Linking
Linking์ด๋ ์ฌ๋ฌ ๊ฐ์ฒด๊ฐ ํ๋์ ์คํ์ ์ํด ๊ฒฐํฉํ๋ ๊ฒ์ ์๋ฏธํ๊ณ , Static๊ณผ Dynamic์ด ์๋ค.
๐ช Static vs. Dynamic
- Staticํ ๋ฐฉ์์, ๋ชจ๋ ์์คํ ๋ผ์ด๋ธ๋ฌ๋ฆฌ๋ค์ด ์ด์ง ํ๋ก๊ทธ๋จ์ ๊ฒฐํฉ๋๋ค. (Loader์ ์ํด ๊ฒฐํฉ)
- Dynamicํ ๋ฐฉ์์, ์คํ ์ ๊น์ง ๊ฒฐํฉ์ด ์ฐ๊ธฐ๋๋ค. (๋ฉ์ธ ํจ์๋ง ๊ฒฐํฉ)
๐ช Dynamic Linking
Stub์ด๋ผ๋ ์์ ์ฝ๋ ์กฐ๊ฐ์ด binary(code)์ ์กด์ฌํ์ฌ ๋ผ์ด๋ธ๋ฌ๋ฆฌ ์ฐธ์กฐ์์ ์ฌ์ฉ๋๋ค.
- ๋ผ์ด๋ธ๋ฌ๋ฆฌ๊ฐ ์ ๋ฐ์ดํธ๋์ด๋, ๋ชจ๋ ํ๋ก๊ทธ๋จ์ด relinkingํ๋ ๊ฒ์ ๋ง๋๋ค. (๋์ ์ผ๋ก ์ฐธ์กฐํ๊ธฐ ๋๋ฌธ์)
๐งท Swapping
์ด๋ ์คํ๋์ง ์์ ํ๋ก์ธ์ค๋ฅผ ๋บ๋ค๊ฐ ๊ทธ ์๋ฆฌ์ ์คํ๋ ํ๋ก์ธ์ค๋ฅผ ๋ฃ๋ ๋ฐฉ์์ด๋ค.
- ์ ํ๋ ๋ฉ๋ชจ๋ฆฌ์์ ๋ง์ ์์ฉ ํ๋ก๊ทธ๋จ๋ค์ ์คํ์ํค๊ธฐ ์ํด์ ํ์ํ๋ค.
- ์ฐ์ ์์์ ๋ฐ๋ผ ์ด๋ค ํ๋ก์ธ์ค๋ฅผ in/outํ ์ง ๊ฒฐ์ ํ๊ณ ์ผ๋ฐ์ ์ผ๋ก ์ค๊ธฐ ์ค์ผ์ค๋ฌ์ ์ํด ์ ์ ํ๋ค.
- backing store: ๋ชจ๋ ๋ฉ๋ชจ๋ฆฌ ๋ณต์ฌ๋ณธ์ ์์ฉํ๊ธฐ์ ์ถฉ๋ถํ ํฐ ๋น ๋ฅธ ๋์คํฌ๋ก, ๋ฉ๋ชจ๋ฆฌ์ ์ง์ ์ ๊ทผ์ด ๊ฐ๋ฅํ ๊ณต๊ฐ์ด๋ค.
- swap in, out: ๋ฉ์ธ ๋ฉ๋ชจ๋ฆฌ์ ๋ค์ด๊ฐ ๋์ ๋์ฌ ๋๋ฅผ ์๋ฏธํ๋ค.
๋ง์ฝ, Compile time์ด๋ Load time binding์ธ ๊ฒฝ์ฐ ์๋ ๋ฉ๋ชจ๋ฆฌ ์์น๋ก swap inํด์ผ ํ๊ณ , Execution time binding์ธ ๊ฒฝ์ฐ ๋น ๋ฉ๋ชจ๋ฆฌ ์์ญ ์๋ฌด ๊ณณ์๋ swap inํ ์ ์๋ค.
๐ช Context Switch Time Including Swapping
swap time์ ์ฃผ๋ ์๊ฐ์ ์ ์ก ์๊ฐ์ผ๋ก, swap๋ ๋ฉ๋ชจ๋ฆฌ์ ์์ ๋น๋กํ๋ค.
Swapping constraints
- Pending I/O: I/O Completion์ ๋๊ธฐํ๋ ํ๋ก์ธ์ค๋ swap outํ ์ ์๋ค. (๊ฒฐ๊ณผ๋ฅผ ๋ฐ์ ํ๋ก์ธ์ค๊ฐ ์์ด์ง๋ฉด ์๋๋ฏ๋ก)
๐งท Contiguous Allocation
๋ฉ๋ชจ๋ฆฌ๋ ์ผ๋ฐ์ ์ผ๋ก ์ปค๋ ์์ญ๊ณผ ์ฌ์ฉ์ ํ๋ก์ธ์ค ์์ญ์ผ๋ก ๋๋๋ค. ๊ทธ ์ค ์ฌ์ฉ์ ํ๋ก์ธ์ค ์์ญ์ ํ ๋น ๋ฐฉ๋ฒ์ผ๋ก๋ Contiguous Allocation(์ฐ์์ ํ ๋น), Noncontiguous Allocation(๋น์ฐ์์ ํ ๋น) ์ด ์๋ค.
Contiguous Allocation๋ ๊ฐ ํ๋ก์ธ์ค๋ค์ด ์ฐ์์ ์ธ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ ์ฐจ์งํ๊ฒ ๋๋ ๊ฒ์ด๋ค.
- ๊ฐ ํ๋ก์ธ์ค๋ฅผ ๋ฉ๋ชจ๋ฆฌ์ ๋ด๊ธฐ ์ํด ๋ฉ๋ชจ๋ฆฌ๋ ๋ฏธ๋ฆฌ ๊ณต๊ฐ์ ๋ถํ ํด๋๋๋ฐ, ์ด ๋ํ ๊ณ ์ ๋ ํฌ๊ธฐ๋ก ๋๋๋ ๊ณ ์ ๋ถํ ๋ฐฉ์๊ณผ ํ๋ก์ธ์ค ํฌ๊ธฐ์ ๋ฐ๋ผ ๋๋๋ ๊ฐ๋ณ ๋ถํ ๋ฐฉ์์ด ์๋ค.
๊ณ ์ ๋ถํ ๋ฐฉ์์ ๋ถํ ์ ํฌ๊ธฐ๊ฐ ๋ชจ๋ ๋์ผํ๊ฑฐ๋ ๋ค๋ฅผ ์ ์๋ค. 1 ๋ถํ ๋น 1 ๊ฐ์ ํ๋ก์ธ์ค๊ฐ ํ ๋น๋๊ธฐ์ ๋์์ ๋ฉ๋ชจ๋ฆฌ์ ๋ก๋๋๋ ํ๋ก์ธ์ค์ ์๊ฐ ๊ณ ์ ๋๋ค. ๋ ์ํ ๊ฐ๋ฅํ ํ๋ก์ธ์ค์ ์ต๋ ํฌ๊ธฐ๊ฐ ์ ํ๋๋ค.
๊ฐ๋ณ ๋ถํ ๋ฐฉ์์ ํ๋ก์ธ์ค์ ํฌ๊ธฐ๋ฅผ ๊ณ ๋ คํ๊ธฐ์ ๋ถํ ์ ํฌ๊ธฐ๋ ๊ฐ์๊ฐ ๋์ ์ผ๋ก ๋ณํ๋ค. ๊ด๋ฆฌ ๊ธฐ๋ฒ์ด ํ์ํ๋ค.
Contiguous Allocation์์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ๋ถํ ํ๋ ๋จ์๋ Block์ด๊ณ , ํ๋ก์ธ์ค๊ฐ ์ฌ์ฉํ ์ ์๋ Block์ Hole์ด๋ผ๊ณ ํ๋ค.
- ๋ค์ํ ํฌ๊ธฐ์ Hole๋ค์ด ๋ฉ๋ชจ๋ฆฌ์ ํฉ์ด์ ธ ์๊ณ , ํ๋ก์ธ์ค๊ฐ ๋์ฐฉํ๋ฉด ์์ฉ ๊ฐ๋ฅํ Hole์ ํ ๋น์์ผ์ค๋ค.
-
๊ฐ๋ณ ๋ถํ ๋ฐฉ์์์ ๊ฐ์ฅ ์ ์ ํ Hole์ ์ฐพ๋ ๋ฌธ์ ๋ฅผ Dynamic Storage-Allocation Problem์ด๋ผํ๊ณ , ์ธ ์ข ๋ฅ์ ํด๊ฒฐ๋ฒ์ด ์๋ค.
- First-fit
- ํฌ๊ธฐ๊ฐ n ์ด์์ธ Hole ์ค ์ต์ด๋ก ๋ฐ๊ฒฌํ Hole์ ํ ๋นํ๋ ๋ฐฉ๋ฒ
- Best-fit
- ํฌ๊ธฐ๊ฐ n ์ด์์ธ ๊ฐ์ฅ ์์ Hole์ ์ฐพ์ ํ ๋นํ๋ค. Hole์ด ํฌ๊ธฐ ์ ์ ๋ ฌ๋์ง ์์ ๊ฒฝ์ฐ ๋ชจ๋ Hole์ ํ์ํด์ผ ํ๋ค.
- Wort-fit
- ๊ฐ์ฅ ํฐ Hole์ ํ ๋นํ๋ค. ๋ง์ฐฌ๊ฐ์ง๋ก ๋ชจ๋ Hole์ ํ์ํด์ผ ํ๋ค.
๐งท Fragmentation
ํ๋ก์ธ์ค๋ค์ด ๋ฉ๋ชจ๋ฆฌ์ ์ ์ฌ๋๊ณ ์ ๊ฑฐ๋๋ ์ผ์ด ๋ฐ๋ณต๋๋ฉด ํ๋ก์ธ์ค๋ค์ด ์ฐจ์งํ๋ ๋ฉ๋ชจ๋ฆฌ ํ ์ฌ์ด์ ์ฌ์ฉํ์ง ๋ชปํ ๋งํผ์ ์์ ๊ณต๊ฐ๋ค์ด ๋์ด๋๊ฒ ๋๋ ํ์์ ๋งํ๋ค.
- ์ธ๋ถ ๋จํธํ(External)์ ๋ด๋ถ ๋จํธํ(Internal)๋ก ๋๋๋ค.
์ธ๋ถ ๋จํธํ๋ ์ด ๊ณต๊ฐ์ ๊ณ์ฐํ์ ๋, ํ๋ก์ธ์ค๊ฐ ๋ค์ด๊ฐ ์ ์๋ ๋ฉ๋ชจ๋ฆฌ๊ฐ ์์์๋ ๋ถ๊ตฌํ๊ณ ๊ณต๊ฐ๋ค์ด ์ฐ์ํ์ง ์์ ์ฌ์ฉํ ์ ์๋ ๊ฒฝ์ฐ๋ฅผ ๋งํ๋ค.
- ํ๋ก์ธ์ค๋ค์ด ํ ๋น๋ฐ์ ๊ณต๊ฐ ์ฌ์ด์ ๋จ๋ ๊ณต๊ฐ
๋ด๋ถ ๋จํธํ๋ ํ๋ก์ธ์ค๊ฐ ์ฌ์ฉํ๋ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ๋ณด๋ค ๋ถํ ๋ ๊ณต๊ฐ์ด ๋ ์ปค์ ๋ฉ๋ชจ๋ฆฌ๊ฐ ๋จ๋ ๊ฒฝ์ฐ๋ฅผ ๋งํ๋ค.
- ํ๋ก์ธ์ค๊ฐ ํ ๋น๋ฐ์ ๊ณต๊ฐ์์ ์ฌ์ฉ๋์ง ์์ ๊ณต๊ฐ
First fit ๋ฐฉ์์ N blocks๋ฅผ ํ ๋นํ๋ ๊ฒฝ์ฐ 0.5N blocks๋ ์ธ๋ถ ๋จํธํ๋ก ์๋๋ค.
๊ณ ์ ๋ถํ ๋ฐฉ์์ ์ธ๋ถ ๋จํธํ์ ๋ด๋ถ ๋จํธํ ๋ชจ๋ ๋ฐ์ํ ์ ์๊ณ , ๊ฐ๋ณ ๋ถํ ์ ์ธ๋ถ ๋จํธํ๊ฐ ๋ฐ์ํ ์ ์๋ค.
- ๊ฐ๋ณ ๋ถํ ์ ํ๋ก์ธ์ค ํฌ๊ธฐ๋ฅผ ๊ณ ๋ คํ ๋ฐฉ์์ด๋ฏ๋ก ๋ด๋ถ ๋จํธํ๋ ๋ฐ์ํ์ง ์์ง๋ง, ์ธ๋ถ ๋จํธํ๋ ๊ณ ๋ ค๋์ง ์์ ๋ฐ์ํ ์ ์๋ค.
์ธ๋ถ ๋จํธํ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํ ๋ฐฉ๋ฒ์ผ๋ก Compaction(์์ถ) ์ด ์๋ค.
- ์ด๋ ํ๋ก์ธ์ค๊ฐ ์ฌ์ฉํ๋ ๊ณต๊ฐ๋ค์ ํ์ชฝ์ผ๋ก ๋ชฐ์ ๊ณต๊ฐ์ ํ๋ณดํ๋ ๋ฐฉ๋ฒ์ด๋ค.
- ํ์ง๋ง ์ด๋ ๋ฉ๋ชจ๋ฆฌ ์ด๋์ ์๊ตฌํด ๋น์ฉ์ด ๋ง์ด ๋๋ ์์ ์ด๋ค.
๐งท Paging
Noncontiguous Allocation ๋ฐฉ์์ผ๋ก, ์ธ๋ถ ๋จํธํ์ ์์ถ ์์ ์ ๋นํจ์จ์ฑ์ ํด๊ฒฐํ๊ธฐ ์ํ ๋ฐฉ๋ฒ์ด๋ค.
- ๋ฉ๋ชจ๋ฆฌ๋ ํ๋ ์(Frame), ํ๋ก์ธ์ค๋ ํ์ด์ง(Page)๋ผ ๋ถ๋ฆฌ๋ ๊ณ ์ ํฌ๊ธฐ์ ๋ธ๋ก(Block)์ผ๋ก ๋ถ๋ฆฌ๋๋ค.
ํ ํ๋ก์ธ์ค๊ฐ ์ฌ์ฉํ๋ ๊ณต๊ฐ์ ์ฌ๋ฌ Page๋ก ๋๋์ด ๊ด๋ฆฌ๋๊ณ , ๊ฐ๊ฐ์ Page๋ ์์์ ๊ด๊ณ์์ด ๋ฉ๋ชจ๋ฆฌ์ Frame์ ๋งคํ๋์ด ์ ์ฅ๋๋ค.
ํ๋ก์ธ์ค๊ฐ ์์๋๋ก ๋ฉ๋ชจ๋ฆฌ์ ์ ์ฅ๋์ง ์๊ธฐ์ ํ๋ก์ธ์ค๋ฅผ ์คํํ๊ธฐ ์ํด์ page๊ฐ ์ด๋ frame์ ๋ค์ด์๋์ง๋ฅผ ์์์ผ ํ๋ค. ์ด์ ๋ํ ์ ๋ณด๊ฐ page table์ ์ ์ฅ๋์ด ์๊ณ , ์ด๋ฅผ ์ฌ์ฉํด ๋ ผ๋ฆฌ์ ์ฃผ์๋ฅผ ๋ฌผ๋ฆฌ์ ์ฃผ์๋ก ๋ณํํ๋ค.
์ฅ์ ์ผ๋ก๋,
- page๋ค์ด ์ฐ์ํ ํ์๊ฐ ์์ด ์ธ๋ถ ๋จํธํ๋ฅผ ํด๊ฒฐํ ์ ์๋ค.
- ํ ๋น๊ณผ ํด์ ๊ฐ ๋น ๋ฅด๋ค.
- swap out์ด ๊ฐ๋จํ๋ค.
- ์ฝ๋๋ฅผ ์ฝ๊ฒ ๊ณต์ ํ ์ ์๋ค.
๋จ์ ์ผ๋ก๋,
- ๋ด๋ถ ๋จํธํ๋ฅผ ํด๊ฒฐํ์ง ๋ชปํ๋ค.
- page table์ ์ ์ฅํ ๋ฉ๋ชจ๋ฆฌ๊ฐ ์ถ๊ฐ๋ก ์ฌ์ฉ๋๋ค.
- page table์ด ๋ฉ๋ชจ๋ฆฌ์ ์์ฃผํ๊ธฐ์ ๋ฉ๋ชจ๋ฆฌ์ ์ ๊ทผํ๋ ์ฐ์ฐ์ 2๋ฒ์ ๋ฉ๋ชจ๋ฆฌ ์ ๊ทผ์ด ํ์ํ๊ฒ ๋์ด ์๋๊ฐ ๋๋ฆฌ๋ค. (page table์ ์ ๊ทผ + ์ค์ ์ฐ์ฐ)
๋ฐ๋ผ์ ์๋ ํฅ์์ ์ํด ํ๋์จ์ด์ ๋์์ด ํ์ํ๊ณ , ์ด๋ฅผ ์ํด TLB(Translation Look-aside Buffer)๋ฅผ ์ฌ์ฉํ๋ค.
CPU์ ์ํด ๋ง๋ค์ด์ง ๋ ผ๋ฆฌ์ ์ฃผ์๋ Page number์ Page offset์ผ๋ก ๋๋๋ค.
- Page number๋ page table์ ์ธ๋ฑ์ค๋ก์, page table ์ ๊ทผ์์ ์ฌ์ฉ๋๋ค.
- Page offset์ ๋ฌผ๋ฆฌ์ ์ฃผ์๋ฅผ ์ป์ ๋ ์ฌ์ฉ๋๊ณ , page table์ base address์ Page offset์ ๋ํ๋ฉด ๋ฌผ๋ฆฌ์ ์ฃผ์๋ฅผ ๊ตฌํ ์ ์๋ค.
- ๋
ผ๋ฆฌ์ ์ฃผ์ ๊ณต๊ฐ์ ํฌ๊ธฐ๊ฐ , Page size๊ฐ ์ธ ๊ฒฝ์ฐ, Page number๋
m-n bits, Page offset์n bits์ด๋ค.
์ด๋, Page offset์ ๋ํ ํ์ธ์ด ํ์ํ๊ฐ?
- ํ์ํ์ง ์๋ค. Page offset์ limit๋ ์ด๋ฏธ Page size์ ๋ํด ๊ณ ์ ๋์ด ์๊ธฐ ๋๋ฌธ์ด๋ค.
Page table์ ํ๋ก์ธ์ค๋ง๋ค ์กด์ฌํ๋ฉฐ, ๋ฉ์ธ ๋ฉ๋ชจ๋ฆฌ์ ์์ฃผํ๋ค. ๋๋ถ๋ถ์ด ๋งค์ฐ ํฐ ํฌ๊ธฐ๋ฅผ ๊ฐ๊ธฐ ๋๋ฌธ์ ์ด๋ฅผ ๊ตฌํํ๊ธฐ ์ํด ๋น์ผ ๋ ์ง์คํฐ๋ฅผ ์ฌ์ฉํ๋ ๊ฒ์ ๋นํจ์จ์ ์ด๊ธฐ ๋๋ฌธ์ด๋ค.
-
๋ฐ๋ผ์ ๋ฉ์ธ ๋ฉ๋ชจ๋ฆฌ์ ์ด๋ฅผ ์ ์ฅํ๊ณ , PTBR(Page-Table Base Register)๋ผ๋ ๋ ์ง์คํฐ๊ฐ ์ด๋ฅผ ๊ฐ๋ฆฌํค๋๋ก ํ๋ค.
- Context Switch๊ฐ ๋ฐ์ํ๋ ๊ฒฝ์ฐ ์ด ๋ ์ง์คํฐ์ ๋ด์ฉ๋ง ๋ณ๊ฒฝํ๋ฉด ๋๋ค.
๐ช Fragmentation in Paging
Paging์ ์ธ๋ถ ๋จํธํ๋ฅผ ํด๊ฒฐํ ์ ์๋ค. ํ์ง๋ง ๋ด๋ถ ๋จํธํ๋ ์ฌ์ ํ ํด๊ฒฐํ์ง ๋ชปํ๊ณ ์๋ค.
- Page size๋ฅผ ์๊ฒํ์ฌ ๋ญ๋น๋ฅผ ์ค์ผ ์ ์๋ค.
- ํ์ง๋ง Page size๋ฅผ ์๊ฒ ํ๋ฉด, ๋ ๋ง์ page table entry๊ฐ ๋ฐ์ํ๊ณ , ์ค๋ฒํค๋๋ฅผ ๋ฐ์์ํจ๋ค.
- ํฐ Page size๋ disk I/O๋ฅผ ํจ์จ์ ์ด๊ฒ ํ ์ ์๋ค.
๐ช Page Protection
Page table์ Protection bit์ Valid-invalid bit๋ฅผ ์ถ๊ฐํ๋ค.
- Protection bit: Page์ ๋ํ ์ ๊ทผ ๊ถํ (read/write/read-only)
- Valid-invalid bit: valid๋ ํด๋น ์ฃผ์์ frame์ ๊ทธ ํ๋ก์ธ์ค๋ฅผ ๊ตฌ์ฑํ๋ ์ ํจํ ๋ด์ฉ์ด ์์์ ์๋ฏธํ๋ค.
๋ฉ๋ชจ๋ฆฌ ํ ๋น์ด ์ฐ์์ ์ธ ๊ฒฝ์ฐ, Limit๋ง ๋น๊ตํด๋ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ๋ณดํธํ ์ ์์์ง๋ง, Paging์ Noncontiguous(๋น์ฐ์์ ) ํ๊ธฐ์ Valid-invalid bit๋ฅผ ์ด์ฉํด Page ์ ๊ทผ ๊ถํ์ ๊ด๋ฆฌํ๋ค.
๐ช Structure of the Page Table
Page table ๊ณต๊ฐ์ ํจ์จ์ ์ธ ๊ตฌ์ฑ์ ์ํ ๋ช ๊ฐ์ง ๋ฐฉ๋ฒ์ด ์๋ค.
- Multi-level Paging
๋ ผ๋ฆฌ์ ์ฃผ์ ๊ณต๊ฐ์ ์ฌ๋ฌ ๋จ๊ณ์ Page table๋ก ๋ถํ ํ์ฌ ์ค์ง ์ฌ์ฉ๋๋ page์ Page table๋ง ํ ๋นํ๋ ๊ธฐ๋ฒ์ด๋ค.
- ์ฌ์ฉ๋๋ Page table๋ง ๋ก๋ํ๊ธฐ์ ๋ชจ๋ Page๋ฅผ ๋ก๋ํด์ผ ํ๋ ๋ถ๋ด์ ์ค์ผ ์ ์๋ค.
32bit ๋ ผ๋ฆฌ์ ์ฃผ์ ๊ณต๊ฐ์ด๋ผ๋ฉด, 20bits๋ Page number, 12bits๋ Page offset์ ๋ํ๋๋ค. Two-level์ธ ๊ฒฝ์ฐ, Page number๋ 10bits์ Page number์ 10bits์ Page offset์ผ๋ก ๋ ๋๋๊ฒ ๋๋ค.
- Hashed Page Table
Hash table์ ์ด์ฉํ์ฌ Page table์ ๊ด๋ฆฌํ๋ ๊ธฐ๋ฒ์ด๋ค. ์ฃผ์ ๊ณต๊ฐ์ด 32bit๋ณด๋ค ์ปค์ง๋ฉด ๊ณ์ธต Paging์ด ๋นํจ์จ์ ์ด๋ฏ๋ก ์ด ๋ฐฉ์์ ์ฌ์ฉํ๋ค.
- virtual page number๋ฅผ ํด์ฑํ์ฌ Page table์ ์ฐธ์กฐํ๋๋ฐ ์ฌ์ฉํ๋ค.
- ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ฅผ ๋ฐ๋ผ๊ฐ๋ฉด์ Page number๋ฅผ ๋น๊ตํ๊ณ ์ผ์นํ๋ฉด ๋์๋๋ Frame number๋ฅผ ์ป๋๋ค.
- ์ฐ๊ฒฐ๋ฆฌ์คํธ๊ฐ ๊ธธ์ด์ง๋ฉด ๋ค๋ฅธ Page์ ์ ์ฅ๋ ์ ์์ด ๋ ๋ง์ ๋ฉ๋ชจ๋ฆฌ ์ ๊ทผ์ ์ ๋ฐํ ๊ฐ๋ฅ์ฑ์ด ์๋ค.
- Inverted Page Table
์ง๊ธ๊น์ง๋ Page table์ด ๊ฐ Page๋ง๋ค ํ๋์ ํญ๋ชฉ์ ๊ฐ์ก๋ค. ๋ฐ๋๋ก ์ด๋ ๋ฉ๋ชจ๋ฆฌ์ Frame๋ง๋ค ํ ํญ๋ชฉ์ฉ ํ ๋นํ๋๋ฐ, ๊ทธ๋ผ ๋ฌผ๋ฆฌ์ Frame์ ๋์ํ๋ ํญ๋ชฉ๋ง ์ ์ฅํ๋ฉด ๋๊ธฐ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํจ์ฌ ์ ๊ฒ ์ฌ์ฉํ๋ค.
- ๊ฐ Page table entry๋ ๊ฐ ๋ฉ๋ชจ๋ฆฌ์ frame์ด ๋ด๊ณ ์๋ ๋ด์ฉ(PID, ๋ ผ๋ฆฌ์ ์ฃผ์)๋ฅผ ํ์ํ๋ค.
- ๋ค๋ง ํ ์ด๋ธ ์ ์ฒด ํ์์ ๋ฌธ์ ๋ก ์ธํด ๋๋ถ๋ถ Hashed page table๊ณผ ๊ฒฐํฉํ์ฌ ์ฌ์ฉํ๋ค.
- ๊ณต์ ํ์ด์ง๋ฅผ ๊ตฌํํ๊ธฐ ์ด๋ ต๋ค. (ํ๋์ entry๊ฐ ํ๋์ owner๋ง ๊ฐ๋ฆฌํฌ ์ ์๋ค.)
๐งท TLB
Translation Look-aside Buffer๋ ๋ฉ๋ชจ๋ฆฌ ์ฃผ์ ๋ณํ์ ์ํ ๋ณ๋์ ์บ์ ๋ฉ๋ชจ๋ฆฌ๋ก, Page table์์ ๋น๋ฒํ ์ฐธ์กฐ๋๋ ์ผ๋ถ entry๋ฅผ ์บ์ฑํ๊ณ ์๋ค.
- entry๋
<key, value>์์ ๊ฐ์ง๊ณ , key์๋ Page number, value์๋ Frame number๋ฅผ ์ ์ฅํ๋ค.
CPU๋ Page table๋ณด๋ค TLB๋ฅผ ๋จผ์ ์ฐธ์กฐํ์ฌ, ์ํ๋ page๊ฐ ์๋ ๊ฒฝ์ฐ ๋ฐ๋ก frame number๋ฅผ ์ป๊ณ , ๊ทธ๋ ์ง ์์ ๊ฒฝ์ฐ ๋ฉ์ธ ๋ฉ๋ชจ๋ฆฌ๊น์ง ์ ๊ทผํ์ฌ ์ป๋๋ค.
- ์ํ๋ page๊ฐ ์๋์ง ํ์ธํ๊ธฐ ์ํด ์ ์ฒด ํ์์ ์ํํด์ผ ํ์ง๋ง, Parallel Search๊ฐ ๊ฐ๋ฅํด ํ์ ์๊ฐ์ ์ ๋ค.
Context Switch๊ฐ ๋ฐ์ํ๋ ๊ฒฝ์ฐ๋ ์ด๋ป๊ฒ ์ฒ๋ฆฌ๋ ๊น?
-
๋งค Switch๋ง๋ค TLB ์ ์ฒด๋ฅผ ๋น์ฐ๋ ๋ฐฉ๋ฒ์ด ์๋ค.
- ๋น์ฐํ ๋น์ฉ์ด ๋ง์ด ๋๋ ์์ ์ด๋ค.
-
TLB์ ๊ฐ entry๊ฐ ์ด๋ ํ๋ก์ธ์ค๋ฅผ ์ํ ๊ฒ์ธ์ง ์ถ์ ํ์ฌ ์ด์ฉ๋์ง ์๋ entry๋ง ๋น์ฐ๋ ๊ฒ์ด ์ข๋ค.
- ์ด๋ฅผ ์ํด ASID(Address Space Identifier)๋ฅผ ์ด์ฉํ๋ค.
- PID์ ์ ์ฌํ์ง๋ง, 8bit๋ก 32bit์ธ PID๋ณด๋ค ์ ๋ ดํ๋ค.
- ๋์ผํ ASID๋ฅผ ๊ฐ๋ ํ๋ก์ธ์ค๋ผ๋ฆฌ๋ TLB๋ฅผ ๊ณต์ ํ ์ ์์ด TLB๋ฅผ ๋น์ฐ๋ ์ค๋ฒํค๋๋ฅผ ์ค์ผ ์ ์๋ค.
TLB๋ ์บ์ ๋ฉ๋ชจ๋ฆฌ์ด๋ฏ๋ก, miss๊ฐ ๋ฐ์ํ ๊ฒฝ์ฐ HW์ OS๊ฐ ๋ชจ๋ ๊ด์ฌํ๋ค.
- HW๊ฐ Page table์์ ์ ํจํ entry๊ฐ ์๋์ง ํ์ธํ๋ค. ์๋ค๋ฉด Page fault๋ฅผ ๋ฐ์์ํค๊ณ , OS๊ฐ ์ฒ๋ฆฌํ๋๋ก ํ๋ค.
- OS๊ฐ ์๋ก์ด Page number๋ฅผ TLB์ ์ถ๊ฐํ๋ค.
- ๋ํ, ์์ฃผ ์ฌ์ฉํ๊ธฐ์ TLB์ ์ ์งํ๊ณ ์ถ์ entry์ ๊ฒฝ์ฐ๋ ๊ณ ์ ์ํฌ ์ ์๋ค. -> Wired Down
๐งท Segmentation
์๋ฏธ ๋จ์๋ก ํ๋์ ํ๋ก์ธ์ค๋ฅผ ๋๋๋ ๊ฒ์ ๋งํ๋ค. ์๊ฒ๋ ํ๋ก๊ทธ๋จ์ ๊ตฌ์ฑํ๋ ํจ์ ํ๋ํ๋๋ฅผ, ํฌ๊ฒ๋ ํ๋ก๊ทธ๋จ ์ ์ฒด๋ฅผ segment์ ๋จ์๋ก ์ ์ํ ์ ์๋ค.
- ์ผ๋ฐ์ ์ผ๋ก๋ stack, code, data ๋ถ๋ถ์ด ํ๋์ segment๋ก ์ ์๋๋ค.
Segmentation์ ๋
ผ๋ฆฌ์ ์ฃผ์๋ <segment number, offset> ์ผ๋ก ๊ตฌ์ฑ๋๋ฉฐ, ๊ฐ๊ฐ์ segment๋ base, limit, protection bit๋ฅผ ๊ฐ์ง๊ณ ์๋ค.
- ๋ชจ๋ segment์ ์์์ 0์ด๋ค.
- ๋ ผ๋ฆฌ์ ์ฃผ์ ๊ณต๊ฐ์ ์ ๋ ฌ๋์ด ์์ง ์๋ค.
ํํ ์๋ Segment fault๋ ๋ค๋ฅธ segment์ ์ ๊ทผํ๋ ค๋ ๊ฒฝ์ฐ ๋ฐ์ํ๋ค.
์ฅ์ ์ผ๋ก๋,
- Paging๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก segment๋ค์ด ์ฐ์์ ์ผ๋ก ํ ๋น๋ ํ์์๋ค.
- stack๊ณผ heap์ด ๋ ๋ฆฝ์ ์ผ๋ก ์ปค์ง ์ ์๋ค. (Overflow๊ฐ ๋ฐ์ํ์ง ์๋๋ค?)
- segment๋ง๋ค protection์ ๋ฐ๋ก ์ํํ ์ ์๋ค.
๋จ์ ์ผ๋ก๋,
- ๊ฐ๊ฐ์ segment๋ ๋ฐ๋์ ์ฐ์์ ์ผ๋ก ํ ๋น๋์ด์ผ ํ๋ค.